package leetcode;

import java.util.ArrayList;
import java.util.List;

public class MultiplyStrings {
	private String reverse(String a){
		char[] charArray1 = a.toCharArray();
		
		int s = 0,e = a.length()-1;
		
		while(s<e){
			char tmp = charArray1[s];
			charArray1[s] = charArray1[e];
			charArray1[e] = tmp;
			s++;
			e--;
		}
		StringBuilder sBuilder = new StringBuilder();
		int i=0;
		for(i=0;i<charArray1.length;i++){
			sBuilder.append(charArray1[i]);
		}
		
		
		
		return sBuilder.toString();
	}
	
	private void addMidRst(List<Integer> rr, List<Integer> rstIntegers ,int n){
		if(rstIntegers.size()==0){
			rstIntegers.addAll(rr);
		} else{
			int c=0;
			int i=n;
			for(;i-n<rr.size() && i<rstIntegers.size();i++){
				int tmp = rr.get(i-n) + rstIntegers.get(i)+c;
				c = tmp/10;
				rstIntegers.set(i, tmp%10);
			}
			
			if(i-n==rr.size()){
				for(;i<rstIntegers.size();i++){
					int tmp = rstIntegers.get(i)+c;
					c = tmp/10;
					rstIntegers.set(i, tmp%10);
				}
				if(c!=0)
					rstIntegers.add(c);
			} else{
				for(;i-n<rr.size();i++){
					int tmp = rr.get(i-n)+c;
					rstIntegers.add(tmp%10);
					c= tmp/10;
				}
				if(c!=0)
					rstIntegers.add(c);
			}
		}
	}
	public String multiply(String num1, String num2) {
        int c=0;
        String n1 = reverse(num1);
        String n2 = reverse(num2);
        List<Integer> rstIntegers = new ArrayList<Integer>();
        for(int i=0;i<n1.length();i++){
        	c=0;
        	List<Integer> rr = new ArrayList<Integer>();
        	for(int j=0;j<n2.length();j++){
        		int tmp = (n2.charAt(j)-'0')*(n1.charAt(i)-'0')+c;
        		c = tmp/10;
        		int d = tmp%10;
        		rr.add(d);
        	}
        	if(c!=0)
        		rr.add(c);
        	addMidRst(rr, rstIntegers, i);
        }
        StringBuilder sbBuilder = new StringBuilder();
        for(Integer i:rstIntegers){
        	sbBuilder.append(i);
        }
        String rr =  reverse(sbBuilder.toString());
        
		char[] charArray = rr.toCharArray();
		StringBuilder sbbBuilder = new StringBuilder();
		int i=0;
		for(i=0;i<charArray.length && charArray[i]=='0';i++);
		
		if(i==charArray.length){
			sbbBuilder.append("0");
		}
		else{
			for(;i<charArray.length;i++)
				sbbBuilder.append(charArray[i]);
		}
		return sbbBuilder.toString();
    }
	
	public static void main(String[] args){
		MultiplyStrings multiplyStrings = new MultiplyStrings();
		String rt = multiplyStrings.multiply("52", "60");
		System.out.println(rt);
	}
}
